package leetcode.backtrace;

import java.util.*;

/**
 * @Description
 * @Author 26233
 * @Create 2021-04-19 21:33:37
 */

/*
给定一个二叉树，返回所有从根节点到叶子节点的路径。

说明: 叶子节点是指没有子节点的节点。

示例:

输入:

   1
 /   \
2     3
 \
  5

输出: ["1->2->5", "1->3"]

解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3
通过次数108,868提交次数162,328

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-paths
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

public class LeetCode257_BinaryTreePaths {
    public List<String> binaryTreePaths(TreeNode root) {

        String path = String.valueOf(root.val);
        List<String> result = new ArrayList<>();
        binaryTreePaths(root, path, result);

        return result;
    }

    public void binaryTreePaths(TreeNode root, String path, List<String> result) {
        if (root != null){
            if (root.left != null){
                String tempPath = path + "->" + root.left.val;
                binaryTreePaths(root.left, tempPath, result);
            }
            if (root.right != null){
                String tempPath = path + "->" + root.right.val;
                binaryTreePaths(root.right, tempPath, result);
            }

            if (root.left == null && root.right == null){
                result.add(path);
            }
        }
    }

    // 非递归 + bfs + queue
    public List<String> binaryTreePaths2(TreeNode root) {

        List<String> result = new ArrayList<>();

        Queue<TreeNode> nodeQueue = new LinkedList<>();
        Queue<String> pathQueue = new LinkedList<>();

        nodeQueue.add(root);
        String path = String.valueOf(root.val);
        pathQueue.add(path);

        while (!nodeQueue.isEmpty()){
            TreeNode tempNode = nodeQueue.poll();
            String tempPath = pathQueue.poll();

            if (tempNode.left != null){
                nodeQueue.add(tempNode.left);
                pathQueue.add(tempPath + "->" + tempNode.left.val);
            }
            if (tempNode.right != null){
                nodeQueue.add(tempNode.right);
                pathQueue.add(tempPath + "->" + tempNode.right.val);
            }

            if (tempNode.left == null && tempNode.right == null){
                result.add(tempPath);
            }
        }

        return result;
    }
}


 class TreeNode {
    int val;
     TreeNode left;
     TreeNode right;
     TreeNode() {}
    TreeNode(int val) { this.val = val; }
     TreeNode(int val, TreeNode left, TreeNode right) {
         this.val = val;
         this.left = left;
        this.right = right;
     }
 }

